﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Auxiliaries
{
    /// <summary>
    /// Auxiliary and support functions and types
    /// </summary>
    public static class MergeSort
    {
        /// <summary>
        /// Interface providing merge sort accessibility
        /// </summary>
        public interface IMergeSortable
        {
            /// <summary>
            /// Comparisson argument for objects implementing IMergeSortable
            /// </summary>
            UInt64 argument
            {
                get;
            }
        }

        /// <summary>
        /// Recursive vector merge sorting of the AEUCGenSetting array of prepared values
        /// </summary>
        /// <param name="generated_values">Reference to the AEUCSetting array containing all of the values</param>
        /// <param name="str_indx">The starting index of the sort (usually the 0 index)</param>
        /// <param name="end_indx">The end index of the sort (usually the last index)</param>
        /// <returns>A sorted array of GenAEUCSettings</returns>
        public static object[] merge_sort(object[] generated_values, int str_indx, int end_indx)
        {
            object[] tmp = null;
            if (end_indx - str_indx > 1)
            {
                tmp = new object[end_indx - str_indx + 1];

                int tmp1_count = 0;
                int tmp2_count = 0;

                //Recursive call for sorting the first half of the array
                object[] tmp1 = merge_sort((IMergeSortable[])generated_values, str_indx, str_indx + (end_indx - str_indx) / 2 - 1);

                //Recursive call for sorting the second half of the array
                object[] tmp2 = merge_sort((IMergeSortable[])generated_values, str_indx + (end_indx - str_indx) / 2, end_indx);

                //Sort merging the two returned sorted vectors
                for (int i = 0; i < (end_indx - str_indx + 1); i++)
                {
                    //Merging while elements are present in both vectors
                    if (tmp1_count < tmp1.Length && tmp2_count < tmp2.Length)
                    {
                        if (((IMergeSortable)tmp1[tmp1_count]).argument < ((IMergeSortable)tmp2[tmp2_count]).argument)
                        {
                            tmp[i] = tmp1[tmp1_count++];
                        }
                        else
                        {
                            tmp[i] = tmp2[tmp2_count++];
                        }
                    }
                    //When elements are present in one vector, just add it as its already sorted
                    else
                    {
                        if (tmp1_count < tmp1.Length)
                        {
                            tmp[i] = tmp1[tmp1_count++];
                        }
                        else
                        {
                            tmp[i] = tmp2[tmp2_count++];
                        }
                    }
                }
            }
            //Sorting the two element vector
            else if (end_indx - str_indx == 1)
            {
                tmp = new object[2];
                if (((IMergeSortable)generated_values[end_indx]).argument < ((IMergeSortable)generated_values[str_indx]).argument)
                {
                    tmp[0] = generated_values[end_indx];
                    tmp[1] = generated_values[str_indx];
                }
                else
                {
                    tmp[0] = generated_values[str_indx];
                    tmp[1] = generated_values[end_indx];
                }
            }
            //Directly returning the one element vector
            else
            {
                tmp = new object[1];
                tmp[0] = generated_values[str_indx];
            }

            return tmp;
        }
    }
}
